# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 3_tree_traversal.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/12/17 16:40
------------------------------------------
    二叉树的各种遍历
"""
from queue import Queue


class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def create_binary_tree(input_list=None):
    """
        构建二叉树
    """
    if not input_list:
        return None

    data = input_list.pop(0)

    if data is None:
        return None

    node = TreeNode(data)
    node.left = create_binary_tree(input_list)
    node.right = create_binary_tree(input_list)

    return node


def pre_order_traversal(node):
    """
        前序遍历
        node,二叉树节点
    """
    if not node:
        return

    print(node.data)
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)

    return node


def in_order_traversal(node):
    """
        中序遍历
    """
    if not node:
        return

    in_order_traversal(node.left)
    print(node.data)
    in_order_traversal(node.right)

    return node


def post_order_traversal(node):
    """
        后续遍历
    """
    if not node:
        return

    post_order_traversal(node.left)
    post_order_traversal(node.right)
    print(node.data)

    return node


def pre_order_traversal_with_stack(node):
    """
        二叉树，非递归前序遍历
    """
    stack = []
    while node or stack:
        while node:
            print(node.data)
            stack.append(node)
            node = node.left

        if stack:
            node = stack.pop()
            node = node.right


def level_order_traversal(node):
    """
        [2021-12-21]
        广度优先-层序遍历
        啊哈，自己先按照自己的思路写的，和答案一模一样
    """
    queue = Queue()
    queue.put(node)

    while queue:
        node = queue.get()
        print(node.data)

        left_node = node.left
        right_node = node.right

        if left_node:
            queue.put(left_node)

        if right_node:
            queue.put(right_node)


def demo():
    """
            3
           /\
          2  8
         /\   \
        9 10   4
    """
    my_input_list = [3, 2, 9, None, None, 10, None, None, 8, None, 4]
    root = create_binary_tree(my_input_list)

    print("前序遍历： ")
    pre_order_traversal(root)

    print("中序遍历： ")
    in_order_traversal(root)

    print("后序遍历：")
    post_order_traversal(root)

    print("层序遍历：")
    level_order_traversal(root)

    """
    out:
    前序遍历： 
        3
        2
        9
        10
        8
        4
        中序遍历： 
        9
        2
        10
        3
        8
        4
        后序遍历：
        9
        10
        2
        4
        8
        3
        层序遍历：
        3
        2
        8
        9
        10
        4
    """


if __name__ == '__main__':
    demo()
